- 原文：Champagne SuperNova, incrementally verifiable computation
- 作者：Not a Monad Tutorial
- 译者：Kurt Pan
引言
非均匀IVC（NIVC)的计算模型
We can think of the program as a collection of $n+1$ non-deterministic, polynomial time computable functions, $f_1, f_2, \ldots, f_n, \phi$, where each function receives $k$ input and $k$ output variables; each $f_j$ can also take non-deterministic input. The function $\phi$ can take non-deterministic input variables and output an element $j=\phi(z=(x, w))$, choosing one of the $f_i$. Each function is represented as a quadratic rank-one constraint system (R1CS), an NP-complete problem. In IVC, the prover takes as input at step $k\left(k, x_0, x\right)$ and a proof $\Pi_k$ that proves knowledge of witnesses $\left(w_0, w_1, \ldots, w_{k-1}\right)$ such that \(x_{j+1}=F\left(x_j, w_j\right)\) for all $j=0,1, \ldots, k$ we have $x=x_{k+1}$. In other words, given a proof that shows that the previous step has been computed correctly and the current state $x_k$, we get the next state $x_{k+1}$ and a proof $\Pi_{k+1}$ showing that we computed step $k$ correctly. In the NIVC setting, $\phi$ selects which function we are going to use, \(x_{j+1}=F_{\phi\left(x_j, w_j\right)}\left(x_j, w_j\right)\) At each step, SuperNova folds an $\mathrm{R} 1 \mathrm{CS}$ instance and its witness, representing the last step of the program’s execution into a running instance (it takes two $N$-sized NP instances into a single $N$-sized NP instance). The prover uses an augmented circuit containing a verifier circuit and the circuit corresponding to the function $f_j$ being executed. The verifier circuit comprises the non-interactive folding scheme and a circuit for computing $\phi$. We will represent the augmented functions as $f_j^{\prime}$
One problem with the folding scheme is that we have multiple instructions, each having its R1CS representation. We could take the path of universal circuits, but this would make us pay a high cost for many cheap instructions. In Nova, we avoided the problem since we only had one type of instruction. To deal with multiple instructions, SuperNova works with $n$ running instances $U_i$, where $U_i(j)$ attests to all previous executions of $f_j^{\prime}$, up to step $i-1$. Therefore, checking all $U_i$ is equivalent to checking all $i-1$ steps. Each $f_j^{\prime}$ takes as input $u_i$, corresponding to step $i$, and folds it to the corresponding $U_i$ instance. We can think of it as looking at the function we want to execute and performing the instance folding with the one related to the previous executions. By doing so, we pay the cost for each instruction only when it is used, at the expense of keeping more running instances and updating accordingly. The verifier circuit corresponding to $f_j^{\prime}$ does the following steps:
- Checks that $U_i$ and $p c_i=\phi\left(x_{i-1}, w_{i-1}\right)$ (the index of the function executed previously) are contained in the public output of the instance $u_i$ . This enforces that the previous step produces both $U_i$ and $p c_i$.
- Runs the folding scheme’s verifier to fold an instance and updates the running instances, $U_{i+1}$.
- Calls $\phi\left(x_i, w_i\right)=p c_{i+1}$ to obtain the index of the following function to invoke.
总结
IVC is a powerful cryptographic primitive which allows us to prove the integrity of computation in an incremental fashion. This strategy is well-suited for virtual machine executions and general programs with dynamic flow control. We could achieve this by using universal circuits, but at the expense of a considerable cost for each instruction, no matter how cheap it could be. Nova introduced folding schemes, allowing one to realize IVC for a single instruction. SuperNova generalizes Nova to multiple instructions by adding a selector function $\phi$, choosing the instruction to be executed at each step. To support several instructions, SuperNova needs to maintain separate bookkeeping for each function’s execution. This construction has many exciting applications since we could realize IVC without requiring expensive arbitrary circuits.